//给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。
//O(n^2)
for (int i = 0; i < n; i++) 
{
    f[i] = 1;    // 设f[i]默认为1，找不到前面数字小于自己的时候就为1
    for (int j = 0; j < i; j++) 
    {
        if (w[i] > w[j]) f[i] = max(f[i], f[j] + 1);    // 前一个小于自己的数结尾的最大上升子序列加上自己，即+1
    }
    ans = max(ans, f[i]);
}
//贪心O(nlogn)
// 状态表示：f[i]表示长度为 i 的最长上升子序列，末尾最小的数字。
// 状态计算：对于每一个w[i], 如果大于f[cnt](下标从1开始，cnt长度的最长上升子序列，末尾最小的数字)，那就cnt+1，使得最长上升序列长度+1，当前末尾最小元素为w[i]。 
// 若w[i]小于等于f[cnt-1],说明不会更新当前的长度，但之前末尾的最小元素要发生变化，找到第一个 大于或等于 (这里不能是大于) w[i]，更新以那时候末尾的最小元素。
// f[i]一定以一个单调递增的数组，所以可以用二分法来找第一个大于或等于w[i]的数字。

vector<int>stk;//模拟堆栈
stk.push_back(arr[0]);
for (int i = 1; i < n; ++i) {
    if (arr[i] > stk.back())//如果该元素大于栈顶元素,将该元素入栈
        stk.push_back(arr[i]);
    else//替换掉第一个大于或者等于这个数字的那个数
        *lower_bound(stk.begin(), stk.end(), arr[i]) = arr[i];
}
cout << stk.size() << endl;
//这个栈【不用于记录最终的最长子序列】，而是【长度为i的递增子串中，末尾元素最小的是stk[i]】，对于同样长度的子串，当然希望它的末端越小越好

//最长公共子序列
for(int i = 1 ; i <= n ; i++)
    for(int j = 1 ; j <= m ; j++)
        {
            f[i][j] = max(f[i - 1][j] , f[i][j - 1]);//那么此时f[i][j]的值肯定不会大于f[i - 1][j]和f[i][j - 1]的最大值，那么一定会等于f[i - 1][j]和f[i][j - 1]的最大值
            if(a[i] == b[j]) f[i][j] = max(f[i][j] , f[i - 1][j - 1] + 1);//如果相同转移
        }                                                       

cout << f[n][m] << endl;
//滚动数组优化
int dp1[5001],dp2[5001];            //此处用两个滚动数组记录，一个记录之前的状态，一个记录此时的状态
for(int i = 1; i<=n; i++)
{
    for(int j = 1; j <= n; j++)
        if(str1[i] == str2[j])                     
            dp1[j] = dp2[j-1]+1;                //“发现”匹配就记录
        else
            dp1[j] = max(dp1[j-1],dp2[j]);        //不匹配就匹配后面的状态 
    memcpy(dp2, dp1, sizeof(dp1));                //记录之前的状态“滚动”匹配 
}

// 给定两个字符串 A和 B，现在要将 A 经过若干操作变为 B，可进行的操作有：删除–将字符串 A 中的某个字符删除。
// 插入–在字符串 A 的某个位置插入某个字符。
// 替换–将字符串 A 中的某个字符替换为另一个字符。
// 现在请你求出，将 A 变为 B 至少需要进行多少次操作。

// f[i][j] 集合：将a[1~i]变成b[1~j]的操作方式
// 1)删除操作：把a[i]删掉之后a[1~i]和b[1~j]匹配
//             所以之前要先做到a[1~(i-1)]和b[1~j]匹配
//             f[i-1][j] + 1
// 2)插入操作：插入之后a[i]与b[j]完全匹配，所以插入的就是b[j] 
//             那填之前a[1~i]和b[1~(j-1)]匹配
//             f[i][j-1] + 1 
// 3)替换操作：把a[i]改成b[j]之后想要a[1~i]与b[1~j]匹配 
//             那么修改这一位之前，a[1~(i-1)]应该与b[1~(j-1)]匹配
//             f[i-1][j-1] + 1
// 但是如果本来a[i]与b[j]这一位上就相等，那么不用改，即
// f[i-1][j-1] + 0

//初始化
for(register int i=1; i<=lena; i++) f[i][0] = i;
for(register int i=1; i<=lenb; i++) f[0][i] = i;

for(register int i=1; i<=lena; i++) {
    for(register int j=1; j<=lenb; j++) {
        f[i][j] = min(f[i-1][j]+1,f[i][j-1]+1);
        if(a[i]==b[j]) f[i][j] = min(f[i][j],f[i-1][j-1]);
        else f[i][j] = min(f[i][j],f[i-1][j-1]+1);
    }
}
printf("%d\n",f[lena][lenb]);


//最大子段和
for (int i = 1; i <= n; i++)
{
    dp[i] = max(dp[i - 1] + a[i], a[i]);
    res = max(res, dp[i]);
}

//二维最大矩阵和
void solve(){
    int n,m;
    cin >> n >> m;
    vector<vector<int>> sum(n + 10,vector<int>(m + 10));
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= m; j ++)
        {
            char c;
            cin >> c;
            if (c == '1') sum[i][j] = sum[i][j - 1] + 1;
            else if (c == '0') sum[i][j] = sum[i][j - 1] - 1;
        }
    }
    vector<int> f(n + 10);

    int ans = 0;
    for(int i = 1; i <= m; i ++){
        for(int j = i; j <= m; j ++)
        {
            for(int k = 1; k <= n; k ++)
            {
                f[k] = sum[k][j] - sum[k][i - 1];
            }
            for(int k = 1; k <= n; k ++)
            {
                f[k] = max(f[k],f[k - 1] + f[k]);
                ans = max(ans,f[k]);
            }
        }
    }
    cout << ans << endl;
}



